/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package problema;

/**
 *
 * @author Antonio
 */
public abstract class Problema<P, S> {

    protected int numSoluzioni;
    protected int solTrovate;

    protected abstract P primoPuntoDiScelta();

    protected abstract P prossimoPuntoDiScelta(P ps);

    protected abstract P ultimoPuntoDiScelta();

    protected abstract S primaScelta(P ps);

    protected abstract S prossimaScelta(S s);

    protected abstract S ultimaScelta(P ps);

    protected abstract boolean assegnabile(S scelta, P puntoDiScelta);

    protected abstract void assegna(S scelta, P puntoDiScelta);

    protected abstract void deassegna(S scelta, P puntoDiScelta);

    protected abstract P precedentePuntoDiScelta(P puntoDiScelta);

    protected abstract S ultimaSceltaAssegnataA(P puntoDiScelta);

    protected abstract void scriviSoluzione(int numSol);

    public void risolvi() {

        P ps = primoPuntoDiScelta();
        S s = primaScelta(ps);

        boolean backtrack = false;
        boolean fine = false;

        do {

            while (!backtrack && solTrovate < numSoluzioni) {
                if (assegnabile(s, ps)) {

                    assegna(s, ps);
                    if (ps.equals(ultimoPuntoDiScelta())) {

                        ++solTrovate;
                        scriviSoluzione(solTrovate);
                        deassegna(s, ps);
                        if (!s.equals(ultimaScelta(ps))) {

                            s = prossimaScelta(s);
                        } else {

                            backtrack = true;
                        }
                    } else {

                        ps = prossimoPuntoDiScelta(ps);
                        s = primaScelta(ps);
                    }
                } else if (!s.equals(ultimaScelta(ps))) {

                    s = prossimaScelta(s);
                } else {

                    backtrack = true;
                }
            }

            fine = ps.equals(primoPuntoDiScelta()) || solTrovate == numSoluzioni;

            while (backtrack && !fine) {

                ps = precedentePuntoDiScelta(ps);
                s = ultimaSceltaAssegnataA(ps);

                deassegna(s, ps);
                if (!s.equals(ultimaScelta(ps))) {

                    s = prossimaScelta(s);
                    backtrack = false;
                } else if (ps.equals(primoPuntoDiScelta())) {

                    fine = true;
                }
            }
        } while (!fine);
    }
}
